package sword.chapter5HashMap;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * RandomizedSet
 * insert remove getRandom O(1)
 * map的key存值，value存list的下标；list的元素存值
 * 删除时，将list的最后一个元素移动到被删除元素的位置。map更新list最后一个元素的下标位置，删除指定值
 *
 * @author K
 * @date 2021-12-01 20:14
 */
public class S30RandomizedSet {
    HashMap<Integer, Integer> map = new HashMap<>();
    ArrayList<Integer> list = new ArrayList<>();

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, list.size());
        list.add(val);
        return true;

    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        Integer index = map.get(val);
        Integer lastValue = list.get(list.size() - 1);
        list.set(index, lastValue);
        list.remove(list.size() - 1);
        map.put(lastValue, index);
        map.remove(val);
        return true;
    }

    public Integer getRandom() {
        Random random = new Random();
        int i = random.nextInt(list.size());
        return list.get(i);
    }

    public static void main(String[] args) {
        S30RandomizedSet set = new S30RandomizedSet();
        set.insert(7);
        set.insert(8);
        set.insert(9);
        set.insert(5);
        set.insert(6);

        set.remove(9);

        Integer result = set.getRandom();
        System.out.println();
    }
}
